import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
	Set hset = new HashSet();
	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num.length < 3) return res;
        
        for (int i = 0; i < num.length - 2; i++) {
	    int need = -num[i];
	    int j = i+1, k = num.length -1;
	    while (j < k) {
		if (num[j] + num[k] == need) {
		    ArrayList<Integer> sol = new ArrayList<Integer>();
		    sol.add(num[i]);
		    sol.add(num[j]);
		    sol.add(num[k]);
		    if (hset.add(sol)) {
			res.add(sol);
		    }
                    j++;
                    k--;
		} else if (num[j] +num[k] < need) {
		    j++;
		} else {
		    k--;
		}	
		
	    }
        //  return res;
        }
        return res;
    }
}
